倒數兩天了~ 今天想再回去看一下資料結構的部分，之前的十二天-C++-資料結構跟十三天-C++-資料結構-二有分別介紹了四種資料結構 Array, Linked List, Stack, Queue ，當然資料結構不只這簡單的四種

今天就來看看樹的資料結構吧~

C++ Tree

首先先來介紹一下樹的概念，是由很多個節點(node)透過邊界(edge)相連而成，通常會由一個節點開始連出去: 根(root)，我們平時在使用的檔案系統就是一種樹，所以很多時候會看到 根目錄 這樣的關鍵字，還有就是樹是不能有環的，也就是這些點最後不會連起來像個圓，而是會擴散出去

這邊紀錄一下樹的關鍵字

• Node 節點: 進行延伸拓展的點、被延伸拓展的點。
• Branch 枝: 延伸拓枝所用到的邊界。分枝(Branching) 一個點藉由邊往外延伸拓展。
• Root 根: 一棵樹的起頭節點。
• Leaf 葉: 在一棵樹上定根後，由根不斷分枝，途中所有無法繼續分枝的點都是葉。
• Level 層: 在一棵樹上定根後，按照拓展的順序(點離根的距離)，可以將樹上的點分層次，使樹上的每個點都屬於一個層數。
• Parent & Child 父 & 子 節點: 在一棵樹上定根後，以邊相連的任兩點，靠近根者為父節點，靠近葉者為子節點。

在看完上述有關樹的介紹，多半都會好奇所以樹是在幹嘛?

這邊就要來提到Binary Search Tree(BST)，二元搜尋樹

這個東西我們程式中常常會用到的工具 資料庫 可是十分活用的，著名的像是MySQL - innodb 裡面的 B+樹，是用來存放索引(index)

目的是為了加快查詢時間，一般像我們之前的章節儲存一系列的資料可能會放陣列(Array)或鏈結串列(Linked List)，但這種在查詢的時候他的成本都是 O(n)，而如果使用BST 二元搜尋樹，查詢的成本可以是 O(log n)

那今天就先到這邊啦~ 明天最後一天目標就是把BST 二元搜尋樹實作出來，以及其他的樹種囉!

很抱歉內容越來越少啦~ 最近事情有點多，所以腦袋也怪怪的 哈~ 但是還是會在最後一天去列出我感覺我自己欠的東西在一個TODO上面，認認真真的回債! 明天見囉

參考資料

Data Structure and Algorithms - Tree
Tree